package com.jjlin.chapter_3;
import java.util.*;
public class CD162 {

    //二叉树节点
    public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int data){
            this.val = data;
        }
    }

    //建立二叉树
    public static TreeNode createBinaryTree(int[][] nums, int root){
        HashMap<Integer, TreeNode> map = new HashMap<>();
        int len = nums.length;
        for(int i = 0; i < len; i++){
            map.putIfAbsent(nums[i][0], new TreeNode(nums[i][0]));
            if(nums[i][1] != 0){
                map.putIfAbsent(nums[i][1], new TreeNode(nums[i][1]));
                map.get(nums[i][0]).left = map.get(nums[i][1]);
            }
            if(nums[i][2] != 0){
                map.putIfAbsent(nums[i][2], new TreeNode(nums[i][2]));
                map.get(nums[i][0]).right = map.get(nums[i][2]);
            }
        }
        return map.get(root);
    }

    //获取二叉树的高度
    public static int getHeight(TreeNode root, int level){
        if(root == null)
            return level;
        return Math.max(getHeight(root.left, level + 1), getHeight(root.right, level + 1));
    }

    //按照标准1打印
    public static void printEdge1(TreeNode root){
        if(root == null)
            return;
        int height = getHeight(root, 0); // 获取二叉树的高度
        TreeNode[][] edgeMap = new TreeNode[height][2]; //获取每一层的最左右节点
        setEdgeMap(root, 0, edgeMap); //获取每一层的最左右节点
        for(int i = 0; i < height; i++) //打印左边界
            System.out.print(edgeMap[i][0].val + " ");
        printLeafNotInMap(root, 0, edgeMap); //打印既不是左边界也不是右边界的叶子节点
        for(int i = height - 1; i >= 0; i--){ //打印右边界，且不是左边界的节点
            if(edgeMap[i][0] != edgeMap[i][1])
                System.out.print(edgeMap[i][1].val + " ");
        }
        System.out.println();
    }

    //获取每一层的最左、最右节点（保存在edgeMap中）
    public static void setEdgeMap(TreeNode root, int level, TreeNode[][] edgeMap){
        if(root == null)
            return;
        edgeMap[level][0] = edgeMap[level][0] == null ? root : edgeMap[level][0];
        edgeMap[level][1] = root;
        setEdgeMap(root.left, level + 1, edgeMap);
        setEdgeMap(root.right, level + 1, edgeMap);
    }

    //获取每一层的最左、最右节点的另一种写法的非递归写法（保存在edgeMap中）
    public static void setEdgeMap1(TreeNode root, TreeNode[][] edgeMap){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0;
        while(!queue.isEmpty()){
            int size = queue.size(); // 每一层的节点数
            for(int i = 0; i < size; i++){
                TreeNode cur = queue.poll();
                if(cur.left != null)
                    queue.offer(cur.left);
                if(cur.right != null)
                    queue.offer(cur.right);
                if(i == 0)  //保存第level层的最左节点
                    edgeMap[level][0] = cur;
                if(i == size - 1) //保存第level层的最右节点
                    edgeMap[level][1] = cur;
            }
            level++;
        }
    }

    //打印既不是左边界也不是右边界的叶子节点
    public static void printLeafNotInMap(TreeNode root, int level, TreeNode[][] edgeMap){
        if(root == null)
            return;
        if(root != edgeMap[level][0] && root != edgeMap[level][1] && root.left == null && root.right == null)
            System.out.print(root.val + " ");
        printLeafNotInMap(root.left, level + 1, edgeMap);
        printLeafNotInMap(root.right, level + 1, edgeMap);
    }

    //按照标准2打印
    public static void printEdge2(TreeNode root){
        if(root == null)
            return;
        System.out.print(root.val + " ");
        if(root.left != null && root.right != null){
            printLeftEdge(root.left, true);
            printRightEdge(root.right, true);
        }else
            printEdge2(root.left == null ? root.right : root.left);
    }

    public static void printLeftEdge(TreeNode root, boolean print){
        if(root == null)
            return;
        if(print || (root.left == null && root.right == null))
            System.out.print(root.val + " ");
        printLeftEdge(root.left, print);
        printLeftEdge(root.right, print && root.left == null);
    }

    public static void printRightEdge(TreeNode root, boolean print){
        if(root == null)
            return;
        printRightEdge(root.left, print && root.right == null);
        printRightEdge(root.right, print);
        if(print || (root.left == null && root.right == null))
            System.out.print(root.val + " ");
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int root = sc.nextInt();
        int[][] nums = new int[n][3];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < 3; j++)
                nums[i][j] = sc.nextInt();
        }
        TreeNode head = createBinaryTree(nums, root);
        printEdge1(head);
        printEdge2(head);
    }
}
